package HashMap;

/**
 * @author zxc
 * @date 2023/04/12 20:32
 **/
// 手写hashmap ：数组 + 链表（尾插法）
public class MyHashMap<K , V> {

    // 2.定义Node节点，用来存储所要存储到hashmap中的数据;
    class Node<K , V>{
        private K key;
        private V value;
        private Node<K , V> next;
        // 无参/有参构造方法
        public Node(){};
        public Node(K key , V value){
            this.key = key;
            this.value = value;
        }
        public Node(K key , V value , Node<K , V> next){
            this.key = key;
            this.value = value;
            this.next = next;
        }
    }

    // 1.自定义hashmap中所拥有的成员变量 ：默认容量，负载因子，对象桶数组和当前所存储到元素个数;
    private final Integer DEFAULT_CAPACITY = 16;
    private final Float LOAD_FACTOR = 0.75f;
    private Float load_factor;
    private Node<K , V>[] buckets;
    private Integer size;

    // 构造函数
    public MyHashMap(){
        buckets = new Node[DEFAULT_CAPACITY];
        load_factor = LOAD_FACTOR;
        this.size = 0;
    }

    public MyHashMap(int capacity){
        buckets = new Node[capacity];
        load_factor = LOAD_FACTOR;
        this.size = 0;
    }
    //  传入自定义的负载因子load-factor
    public MyHashMap(float loadFactor){
        buckets = new Node[DEFAULT_CAPACITY];
        this.load_factor = loadFactor;
        this.size = 0;
    }

    public MyHashMap(int capacity , float loadFactor){
        buckets = new Node[capacity];
        this.load_factor = loadFactor;
        this.size = 0;
    }

    // 3.put方法 ：
    public void put(K key , V value){
        // （1）首先，向hashmap中插入元素
        putVal(key , value , buckets);
        // （2）在插入元素后，判断该hashmap是否需要进行扩容;
        if(size >= buckets.length * load_factor){
            resize();
        }
    }

    // 9.根据key，从hashmap中获取对应value;
    public V get(K key){
        // （1）所要查询到key，经过扰动函数后，所得到的新hashcode值
        int hashCode = newHashCode(key);
        // （2）获取其在桶数组中对应索引的下标
        int index = getIndex(hashCode);
        Node<K, V> node = buckets[index];
        // （3）buckets[index]中不存在元素的情况 ：
        if(node == null){
            return null;
        }
        // （4）遍历链表，查找符合和key完全相同的链表节点;
        while(node != null){
            if(node.key.hashCode() == key.hashCode()
                    && node.key.equals(key)){
                return node.value;
            }
            node = node.next;
        }
        // （5）遍历整条链表，未能够找到和key完全相同的链表节点;
        return null;
    }
    // 10.返回当前hashmap中所存储的元素数量
    public int size(){
        System.out.println("hashmap的长度为 ：" + buckets.length);
        return this.size;
    }

    // 6.对于hashmap进行扩容
    private void resize() {
        // （1）新建newBuckets数组，作为扩容后的数组;
        Node<K , V>[] newBuckets = new Node[buckets.length * 2];
        // （2）原桶数组buckets中所有key进行rehash，将其存储到新桶数组newBuckets;
        rehash(newBuckets);
        // （3）最后，将bucket指向扩容后的桶数组newBucket
        buckets = newBuckets;

    }
    // 7.原桶数组buckets中所有key进行rehash，将其存储到新桶数组newBuckets;
    private void rehash(Node<K,V>[] newBuckets) {
        // （1）遍历原数组中所有key ：
        for(int i = 0 ; i < buckets.length ; i++){
            Node<K, V> node = buckets[i];
            // （2）当前遍历的桶元素为空的情况 ：
            if(node == null){
                continue;
            }
            // （3）当前遍历的桶元素不为空，即需要遍历该链表中所有元素 ：
            while (node != null){
                int hashcode = newHashCode(node.key);
                /**
                 * 即，通过 （node.key的hashcode值） & 原桶数组长度，来进行判断；
                 * （1）若是结果为0，则 该元素在新桶数组中位置 = 该元素在原桶数组中位置;
                 * （2）若是结果为1，则 该元素在新桶数组中位置 = 该元素在原桶数组中位置 + 原桶数组长度;
                 */

                if((hashcode & buckets.length) == buckets.length){
                    rehashPutVal(node , i + buckets.length , newBuckets);
                }
                else {
                    rehashPutVal(node , i , newBuckets);
                }
                node = node.next;
            }
        }
    }
    // 8.hashmap扩容时，将所有原桶数组中元素插入到新桶数组的过程
    private void rehashPutVal(Node<K,V> node, int index, Node<K,V>[] newBuckets) {
        // 尾插法 ：
        Node<K, V> newNode = newBuckets[index];
        if(newNode == null){
            newBuckets[index] = node;
            return;
        }
        Node<K ,V> prev = newNode;
        while(newNode != null){
            prev = newNode;
            newNode = newNode.next;
        }
        prev.next = node;
    }

    // 4.向hashmap中插入元素 ：
    private void putVal(K key, V value, Node<K,V>[] buckets) {
        int hashcode = newHashCode(key);
        int index = getIndex(hashcode);
        Node<K , V> node = buckets[index];
        // （1）桶数组位置为空 ：
        if(node == null){
            buckets[index] = new Node<>(key, value);
            size++;
            return;
        }
        // （2）对应的桶数组位置不为空 ：
        //  遍历当前桶数组位置所对应的链表 ：（重复检测）
        Node<K , V> prev = node;
        // prev节点，作用在于 当链表中不存在与key相同的链表节点时，由于使用的是尾插法，该prev节点指向链表尾节点;
        while(node != null){
            // （3）链表中存在链表节点和所要插入key完全相同 :

            // 当前遍历链表节点node满足以下条件 ：
            // 1.node.key 和 key的hashcode值相同;
            // 2.node.key 和 key调用equals方法也是相同的;
            if(node.key.hashCode() == key.hashCode()
                    && node.key.equals(key)){
                node.value = value;
                return;
            }
            prev = node;
            node = node.next;
        }
        // （4）链表中不存在链表节点和所要插入key完全相同 :
        prev.next = new Node<>(key , value);
        size++;
    }

    // 5.即，使用扰动函数对于当前key的hashcode值进行重新计算;
    private int newHashCode(K key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    // 6.根据hashcode值，求解出当前元素在桶数组中对应的下标索引;
    private int getIndex(int hashcode){
        // 由于桶数组的长度为 2的幂次方，所以直接返回 hashcode & （桶数组长度 - 1）即可;
        return hashcode & (buckets.length - 1);
    }


}
